package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/increasing-order-search-tree/description
 *
 * ```
 * 897. 递增顺序搜索树
 * 给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
 *
 * 示例 1：
 * 输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
 * 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
 *
 * 示例 2：
 * 输入：root = [5,1,7]
 * 输出：[1,null,5,null,7]
 * ```
 */
class leetcode_897 {
    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n5 = TreeNode(5)
        val n7 = TreeNode(7)
        val root = n5
        root.left = n1
        root.right = n7
        val actual = increasingBST(root)
        val expected = n1
        Assert.assertEquals(expected, actual)
        Assert.assertEquals(null, actual?.left)
        Assert.assertEquals(n5, actual?.right)
        Assert.assertEquals(n7, actual?.right?.right)
    }


    private fun increasingBST(root: TreeNode?): TreeNode? {
        /**
        题型：二叉树的中序遍历
        思路：
        先使用中序遍历把 节点收集到list中。
        使用dummy 作为根节点，p 为指针指向dummy，遍历list的item，把每个节点添加到右子树，并设置每个节点的left 设置为null
        返回dummy的right 作为 root。
        https://leetcode.cn/problems/increasing-order-search-tree/solutions/742305/gong-shui-san-xie-yi-ti-shuang-jie-di-gu-yc8l
         */
        val list: ArrayList<TreeNode> = ArrayList()
        collectNodes(root, list)
        val dummy: TreeNode = TreeNode(-1)
        var p: TreeNode = dummy
        list.forEach { item ->
            // TODO:item 的左右孩子首先设置为null
            item.left = null
            item.right =  null
            p.right = item
            p = item
        }
        return dummy.right
    }

    private fun collectNodes(root: TreeNode?, list: ArrayList<TreeNode>) {
        // 1 确认函数参数以及返回值
        // 2 确定终止条件
        if (root == null) {
            return
        }
        // 3 确定单层递归的遍历逻辑
        // 左
        collectNodes(root.left, list)

        // 中
        list.add(root)

        // 右
        collectNodes(root.right, list)
    }
}